The present invention belongs to the art of multiple access communications systems such as, but not limited to, wireless Local Area Networks (Wireless LANS), cellular land-mobile communications systems, mobile satellite communications systems, and memory storage and retrieval devices. Such systems are characterized by at least one fixed base or relay station attempting to maintain communications with a plurality of subscriber stations or terminals that are each assigned a different time slot (TDMA), a different frequency slot (FDMA), or different signature waveform (CDMA), to name a few examples.
In such systems, capacity to support a large number of subscribers is measured in units such as bits per second per Hertz per cell or other physical dimension such as a sector in a cellular system or square microns in a disk storage system. (e.g. the sum of the information data rates, Bits/sec, of all the users in the system). Of primary interest is the maximum number of users that can operate within the system without having to decrease the information rate that they are already accustomed to using or increase the total bandwidth occupied by the system. The capacity can be increased by using more MHz of bandwidth, by reducing the area covered by each base station so that there are more base stations per square kilometer, by decreasing the frequency spacing between channels, and by transmitting more than one signal in the same frequency channel or time slot. However, reducing cell size or reducing the number of signals received by the detector is not always possible or economically feasible. When such action is possible, it increases the infrastructure cost. In addition, some of the above listed solutions increase inter-symbol interference (ISI) and multi-user interference (MUI), also called co-channel interference. ISI is caused by a signal being received along with a delayed version thereof caused by a reflection of the signal from an object such as a large building. MUI discoursed by the receipt of another signal having the same frequency, often meant to be received at a different receiver. In addition, received signals are typically corrupted by additive Gaussian noise.
In order to be able to further accommodate increased traffic, and to make maximum utilization of a traffic channel, multiple interfering signals may be transmitted on the same communication channel and are purposely allowed to interfere with one another. The effects of the resulting multi-user interference are then removed at the receiver by a multi-user detector (MUD). Using a MUD does not require a change in the existing transmitted signaling method, making it an attractive option.
To separate multiple interfering signals transmitted on the same communication channel some unique apriori knowledge of each of the signals is required. For this purpose a parameter estimation unit is required, such as disclosed in U.S. Pat. No. 6,947,505 , entitled “System For Parameter Estimation And Tracking Of Interfering Digitally Modulated Signals”. The parameter estimation required to attain this apriori knowledge may be done using “blind” parameter estimation, “non-blind” parameter estimation, or parameter estimation with the aid of training sequences. This last method is typically derived using a “training signal” or other knowledge of received signals in a manner well known in the art. The purpose of the parameter estimation unit is to identify and determine parameters associated with each signal that are required by the multi-user detector (MUD) to separate each signal from the other interfering signals, regardless of the fact that the signals exist in the same communications bandwidth and at the same instant in time. These parameters might include the received power, the phase of the oscillator which generated each received signal, the timing offset relative to the base station clock, carrier frequency, any frequency offset of the carrier, the assigned spreading code, and the structure of multi-path replicas.
To successfully demodulate simultaneously occurring interfering signals, signal processing of the received signal is accomplished utilizing multi-user detection (MUD) techniques. Early work in MUD, described in Multi-user Detection by S. Verdu, Cambridge University Press, 1998 proposed using computationally intense maximum likelihood (ML) exhaustive search techniques to separate the interfering signals. In certain applications, linear MUD detectors with lower computational demands may be used, and such MUD detectors are described by Verdu. However, the reduction in performance, particularly in high-interference situations, is so significant as to make those reduced complexity techniques not applicable. One method of implementing a ML is the well-known decoder known as the Viterbi decoder. A Viterbi decoder is based upon the Viterbi algorithm and performs a breadth first decoding search of all paths through an entire code tree (or trellis, which is a more compact representation of the code tree) by extending paths through the tree and the entire tree is searched. The complexity of the maximum likelihood (ML) Viterbi decoder in the context of many applications is prohibitively high.
The M-algorithm is a tree-pruning technique that approximates the operation of a ML Viterbi decoder at reduced complexity. The M-algorithm is a breadth first decoding algorithm, but with the M algorithm only the best M paths are retained at each level in the tree. This reduced tree search, referred to as “tree pruning”, reduces the number of calculations that must be made and therefore speeds the overall tree processing.
Viterbi algorithm decoders and M algorithm decoders are also well known in the art as maximum likelihood decoders which can be used in systems that employ error correcting codes, such as convolutional codes, tree codes, and a variety of other codes, all of which can be generally characterized by a tree. The basic concept of these decoders can be described as correlating all possible transmitted sequences with the received sequence and then choosing as the “best” or “maximum likelihood” path the sequence whose correlation is a maximum.
A tree consists of a sequence of concatenations of a so-called tree diagram, or state transition diagram. The tree diagram defines, for each code state, which next state or states the encoder is allowed to transition to. The allowable transitions from one state to a next state are limited. Each possible transition from one state to a next state in a tree is called a branch. Each branch, therefore, corresponds to a subset. A sequence of signal points selected from a sequence of interconnected branches is called a path through the tree.
Transmitted signal points in signal space are displaced at the receiver due to noise and channel-induced distortion. In the case of a single transmitter and inter-symbol interference (ISI), or employment of a convolutional error correction code, a receiver may use a Viterbi algorithm decoder or an M algorithm decoder, operating on a received version of the stream of transmitted signal points, to perform the aforementioned maximum likelihood sequence detection or an approximation of ML sequence detection, respectively. Based on the received version of the transmitted signal points and the knowledge of the tree code used by the encoder and/or the ISI structure, the decoder determines the most likely sequence of signal points that was actually transmitted. The decoder performs this function by forming a decision as to what was the most likely transmitted signal point that would have caused the encoder to transition into a next state of the code. The technique works on concepts that can be modeled as a progression of states that branch out in a tree form of. In the case of interfering signals, a tree can be formed that represents all possible choices of the transmitted values for all signals. That is, error correction coding is not necessarily assumed for tree decoding and doesn't necessarily dictate the formation of the tree. Rather, the tree is formed by the fact that different hypotheses for the received sequences are possible.
More particularly, a Viterbi algorithm decoder, an M algorithm decoder, or any other tree-search decoder forms paths through a tree by keeping track of so-called “metrics”. A branch metric, a function of the received version of the signal point, is calculated for each current-to-next-state transition associated with each branch in the tree diagram. Every path through the tree which leads into a state has an associated path metric which is a function of the sum of the branch metrics for the branches that make up that particular path. Further, a path entering a current state may be extended through the tree and enter a next state by including a branch representing an allowed transition from the current state to the next state. The path metric for such an extended path is a function of the sum of (a) the path metric associated with the path as it entered the current state and (b) the branch metric associated with the included branch.
The Viterbi decoder compares the path metrics of the different paths entering a state and retains as one of the aforementioned surviving paths the path with the smallest path metric. All other paths entering that state are discarded. The surviving paths are used by the decoder to make a final decision as to the value of an earlier transmitted signal point.
To reduce the complexity of the tree search, thereby increasing the speed of testing multiple hypotheses, shortcuts may be deliberately taken in the processing with a tree decoder. For instance, the M-algorithm prunes the tree by retaining, at every stage in the tree, the best M paths through the tree. The computation complexity of a tree search is directly related to the number of hypotheses which must be tested, i.e. the number of paths through the tree which must be examined. For example, for an ML multi-user detector for which there are K interfering by binary phase shift keyed signals and which uses the Viterbi algorithm, the computational complexity is on the order of 2K for each symbol interval. For the M-algorithm, the complexity is on the order of K1.2 for each symbol interval. The reduction in complexity by using the M-algorithm is considerable, but not for very large values of K or for high data rates the complexity reduction is not enough. In addition, tree pruning carries with it the risk that the correct path through the tree is eliminated from consideration, which causes a decoding error. Judicious pruning is required. For the M-algorithm, as M is decreased, the complexity is reduced by the probability of incorrect pruning increases. That is, the need for accuracy limits the reduction in complexity that is feasible. The M-algorithm is described in greater detail further in the Summary of the Invention. See also U.S. Pat. No. 6,151,370 issued Nov. 21, 2000 which describes the M-algorithm. Tree pruning techniques also apply to maximum a posteriori (MAP) decoders.
To further improve the performance of a communication system, some coding schemes include interleavers at the transmitter, which mix up the order of the bits in each packet of bits during encoding. Thus, when interference destroys a few adjacent bits during transmission, the effect of the interference is spread out over the entire original packet and can more readily be overcome by the decoding process. Other improvements may include multiple-component codes which include coding the packet more than once in parallel or in series. However, as this invention is concerned with operation at the receiver, the interleavers included in the receiver are only the interleavers and de-interleavers that are necessary to reverse the operation of any interleaving done at the transmitter.
In short, despite all the decoding processing gains in the art there is still a need for an improved method and apparatus for signal processing simultaneously occurring, interfering signals to speed the decoding processing and allow for acceptable detection performance at real-time operational speeds.